﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

#include <unordered_set>
#include <vector>
class Solutionx {
public:
    int longestConsecutive(vector<int>& nums)
    {
        unordered_set<int> hash;
        for (auto e : nums)
            hash.insert(e);
        int cnt = 0;
        for (auto e : hash)
        {
            if (!hash.count(e - 1))
            {
                int tmp = e;
                while (hash.count(tmp + 1))
                {
                    tmp++;
                }

                cnt = max(cnt, tmp - e + 1);
            }
        }
        return cnt;
    }
};

//int main()
//{
//    vector<int> v = { 100,4,200,1,3,2 };
//    Solutionx s;
//    s.longestConsecutive(v);
//
//    return 0;
//}

//int main()
//{
//    int n = 3;
//    while (n--)
//    {
//        cout << n << " ";
//    }
//    return 0; 
//}


//int main()
//{
//    
//    vector<int> ch = { 1,2,3,4,5,6 };
//    vector<int> res;
//    
//    memcpy(res, ch, sizeof(ch));
//    return 0;
//}
#include <unordered_map>
#include <algorithm>
class Solutionp {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        /*for (auto& e : strs)
        {
            string tmp = e;
            sort(tmp.begin(), tmp.end());
            hash[tmp].emplace_back(e);
        }*/
        for (int i = 0; i < strs.size(); i++)
        {
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            hash[tmp].emplace_back(strs[i]);
        }

        vector<vector<string>> vv;
        /*for (auto& e : hash)
        {
            vv.emplace_back(e.second);
        }*/
        auto ret = hash.begin();
        while (ret != hash.end())
        {
            vv.emplace_back(ret->second);
            ++ret;
        }
        return vv;
    }
};

//int main()
//{
//    Solution s;
//    vector<string> str = { "eat", "tea", "tan", "ate", "nat", "bat" };
//    vector<vector<string>> ret = s.groupAnagrams(str);
//    for (int i = 0; i < str.size(); i++)
//    {
//        cout << str[i] << " ";
//    }
//    return 0;
//}
struct ListNode{
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    
};
class Solutionj {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* cur = head;
        while (cur && cur->next)
        {
            if (cur->val == cur->next->val)
                cur->next = cur->next->next;
            else
                cur = cur->next;
        }
        return head;
    }
};

// 删除链表的倒数第N个结点
class Solutiontc {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        int len = 0;
        ListNode* cur = head;
        while (cur)
        {
            len++;
            cur = cur->next;
        }
        cur = head;
        if (n == len)  return cur->next;
        int del = len - n, x = 0;
        ListNode* prev = nullptr;
        while (cur)
        {
            if (x != del)
            {
                x++;
                prev = cur;
                cur = cur->next;
            }
            else
                break;
        }
        prev->next = cur->next;
        return head;
    }
};


//int main()
//{
//    vector<int> v;
//    cout << sizeof(v) << endl;
//    return 0;
//}

//class Solution {
//public:
//    int findDuplicate(vector<int>& nums)
//    {
//        sort(nums.begin(), nums.end());
//
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (i + 1 != nums[i]);
//                return nums[i];
//        }
//        return nums[nums.size() - 1];
//    }
//};
//int main()
//{
//    Solution sv;
//    vector<int> nums = { 1,3,4,2,2 };
//    int ret = sv.findDuplicate(nums);
//    cout << ret << endl;
//    return 0;
//}

//class Solution {
//public:
//    bool isPalindrome(string s)
//    {
//        string str;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] >= 'A' && s[i] <= 'Z')
//                str += s[i] + 32;
//            if (s[i] >= 'a' && s[i] <= 'z')
//                str += s[i];
//            if (s[i] >= '0' && s[i] <= '9')
//                str += s[i];
//        }
//
//        int left = 0, right = str.size() - 1;
//        while (left < right)
//        {
//            if (str[left] != str[right])
//                return false;
//            left++;
//            right--;
//        }
//        return true;
//    }
//};
//
//int main()
//{
//    Solution s;
//    string sp = "OP";
//    bool ret = s.isPalindrome(sp);
//    cout << ret << endl;
//    return 0;
//}
#include <stack>
//class Solution {
//public:
//    bool isValid(string s)
//    {
//        stack<char> st;
//        if (s.size() % 2 == 1)   return false;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
//            {
//                st.push(s[i]);
//                continue;
//            }
//            if (!st.empty())
//            {
//                if (s[i] == ')' && st.top() == '('
//                    || s[i] == '[' && st.top() == '['
//                    || s[i] == '{' && st.top() == '}')
//                {
//                    st.pop();
//                }
//                else    return false;
//            }
//        }
//        return true;
//    }
//};
//
//int main()
//{
//    string str = "()[]{}";
//    Solution s;
//    bool ret = s.isValid(str);
//    return 0;
//}

// 移掉K位数字
//class Solution {
//public:
//    string removeKdigits(string num, int k)
//    {
//        stack<char> st;
//        for (int i = 0; i < num.size(); i++)
//        {
//            // 若栈顶元素比 当前元素大，则删除栈顶元素
//            while (k && !st.empty() && num[i] < st.top())
//            {
//                st.pop();
//                k--;
//            }
//            if (st.empty() && num[i] == '0') // 处理前导零的情况
//                continue;
//            st.push(num[i]);
//        }
//        string ret;
//        // 处理num为一组递增数列 或 num.size = 1的情况
//        while (!st.empty() && k)
//        {
//            st.pop();
//            k--;
//        }
//        while (!st.empty())
//        {
//            ret += st.top();
//            st.pop();
//        }
//        reverse(ret.begin(), ret.end());
//        return ret.size() == 0 ? "0" : ret;
//    }
//};
// 练习-双指针
//class Solution {
//public:
//    int triangleNumber(vector<int>& nums)
//    {
//        int ret = 0;
//        sort(nums.begin(), nums.end());
//        int n = nums.size() - 1;
//        for (; n >= 2; n--) // 先固定最大的数
//        {
//            // 利用双指针统计符号条件的三元组
//            int left = 0, right = n - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] > nums[n])
//                {
//                    ret += right - left;
//                    right--;
//                }
//                else    left++;
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        int n = nums.size();
//        // 第⼀层循环从前往后列举第⼀个数
//        for (int i = 0; i < n; i++)  
//        {
//            // 第⼆层循环从 i 位置之后列举第⼆个数
//            for (int j = i + 1; j < n; j++)  
//            {
//                // 两个数的和等于⽬标值，说明我们已经找到结果了
//                if (nums[i] + nums[j] == target) 
//                    return { nums[i], nums[j] };
//            }
//        }
//        return { -1, -1 };
//    }
//};

// 最小栈
//class MinStack {
//public:
//    void push(int val)
//    {
//        _stack.push(val);
//        if (_minstack.empty() || val <= _minstack.top())
//        {
//            _minstack.push(val);
//        }
//    }
//
//    void pop()
//    {
//        if (_stack.top() <= _minstack.top())
//        {
//            _minstack.pop();
//        }
//        _stack.pop();
//    }
//
//    int top()
//    {
//        return _stack.top();
//    }
//
//    int getMin()
//    {
//        return _minstack.top();
//    }
//    stack<int> _minstack;
//    stack<int> _stack;
//};
//typedef struct Tree
//{
//    int val;
//    TreeNode* left, * right;
//    Tree() {}
//    ~Tree(){}
//}TreeNode;
#include <queue>
//class Solution {
//public:
//    vector<int> rightSideView(TreeNode* root)
//    {
//        vector<int> v;
//        if (root == nullptr) return v;
//        queue<TreeNode*> q;
//        q.push(root);
//
//        while (!q.empty())
//        {
//            int size = q.size();
//            v.push_back(q.back()->val);
//            for (int i = 0; i < size; i++)
//            {
//                TreeNode* ret = q.front();
//                q.pop();
//                if (ret->left)   
//                    q.push(ret->left);
//                if (ret->right)  
//                    q.push(ret->right);
//            }
//        }
//        return v;
//    }
//};

//class Solution
//{
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> ret;
//        // 1. 排序
//        sort(nums.begin(), nums.end());
//        // 2. 利⽤双指针解决问题
//        int n = nums.size();
//        for (int i = 0; i < n; ) // 固定数 a
//        {
//            if (nums[i] > 0) break; // ⼩优化
//            int left = i + 1, right = n - 1, target = -nums[i];
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right];
//                if (sum > target) right--;
//                else if (sum < target) left++;
//                else
//                {
//                    ret.push_back({ nums[i], nums[left], nums[right] });
//                    left++, right--;
//                    // 去重操作 left 和 right
//                    while (left < right && nums[left] == nums[left - 1]) left++;
//                    while (left < right && nums[right] == nums[right + 1])
//                        right--;
//                }
//            }
//            // 去重 i
//            i++;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};

//class Solution
//{
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target)
//    {
//        vector<vector<int>> ret;
//        // 1. 排序
//        sort(nums.begin(), nums.end());
//        // 2. 利⽤双指针解决问题
//        int n = nums.size();
//        for (int i = 0; i < n; ) // 固定数 a
//        {
//            // 利⽤ 三数之和
//            for (int j = i + 1; j < n; ) // 固定数 b
//            {
//                // 双指针
//                int left = j + 1, right = n - 1;
//                long long aim = (long long)target - nums[i] - nums[j];
//                while (left < right)
//                {
//                    int sum = nums[left] + nums[right];
//                    if (sum < aim) left++;
//                    else if (sum > aim) right--;
//                    else
//                    {
//                        ret.push_back({ nums[i], nums[j], nums[left++],
//                        nums[right--] });
//                        // 去重⼀
//                        while (left < right && nums[left] == nums[left - 1])
//                            left++;
//                        while (left < right && nums[right] == nums[right + 1])
//                            right--;
//                    }
//                }
//                // 去重⼆
//                j++;
//                while (j < n && nums[j] == nums[j - 1]) j++;
//            }
//            // 去重三
//            i++;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};

// 三数之和
//class Solution
//{
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> v;
//        sort(nums.begin(), nums.end());
//        for (int i = nums.size() - 1; i >= 0;)
//        {
//            int target = -nums[i];
//            int right = i - 1, left = 0;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] < target)   left++;
//                else if (nums[left] + nums[right] > target)  right--;
//                else
//                {
//                    v.push_back({ nums[left], nums[right], nums[i] });
//                    left++;     right--;
//                    while (left < right && nums[right + 1] == nums[right])   right--;
//                    while (left < right && nums[left - 1] == nums[left]) left++;
//                }
//            }
//            i--;
//            while (i >= 0 && nums[i] == nums[i + 1]) i--;
//        }
//        return v;
//    }
//};

//class Solution {
//public:
//    int lengthOfLongestSubstring(string s)
//    {
//        unordered_map<char, int> hash;
//        int n = s.size();
//        int left = 0, right = 0;
//        int len = 0;    // 子串长度
//        for (; right < n;)
//        {
//            hash[s[right]]++;
//            while (hash[s[right]] > 1)
//            {
//                hash[s[left]]--;
//                left++;
//            }
//            len = max(len, right - left + 1);
//            right++;
//        }
//        return len;
//    }
//};
//int main()
//{
//    Solution so;
//    string str = "abcabcbb";
//    int ret = so.lengthOfLongestSubstring(str);
//    cout << ret << endl;
//
//    return 0;
//}

//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k)
//    {
//        int len = 0, cnt = 0;
//        for (int left = 0, right = 0; right < nums.size(); right++)
//        {
//            // 进窗口
//            if (nums[right] == 0)    cnt++;
//            while (cnt > k)  //判断
//            {
//                if (nums[left] == 0) cnt--;
//                left++;// 出窗口
//            }
//            // 更新结果
//            len = max(len, right - left + 1);
//        }
//        return len;
//    }
//};

// 正难则反
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x)
//    {
//        int len = nums.size(), sum = 0;
//        for (auto e : nums)  sum += e;
//
//        int target = sum - x, ret = -1;
//        if (target < 0)  return -1;  //细节
//        int add = 0;
//        for (int left = 0, right = 0; right < len; right++)
//        {
//            add += nums[right]; // 进窗口
//            while (add > target) // 判断
//            {
//                add -= nums[left];
//                left++;         // 出窗口
//            }
//            if (add == target)   ret = max(ret, right - left + 1);
//        }
//        return ret == -1 ? -1 : len - ret;
//    }
//};
//class Solution {
//public:
//    int totalFruit(vector<int>& fruits)
//    {
//        // 用一个hash表标记水果的种类
//        unordered_map<int, int> hash;
//        int ret = 0;
//        for (int left = 0, right = 0; right < fruits.size(); right++)
//        {
//            hash[fruits[right]]++;  // 入窗口
//            while (hash.size() > 2)  // 判断，窗口内的种类个数大于2就出窗口
//            {
//                hash[fruits[left]]--;// 出窗口
//                // 若hash表中某个水果种类为0，则直接删除该水果
//                if (hash[fruits[left]] == 0) hash.erase(fruits[left]);
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};
// 二叉树的最大宽度
//class Solution {
//public:
//    int widthOfBinaryTree(TreeNode* root)
//    {
//        unsigned int ret = 0;
//        queue<pair<TreeNode*, unsigned int>> q;
//        q.push({ root, 1 });
//        while (!q.empty())
//        {
//            // 更新当前层的宽度
//            auto end = q.back();
//            auto begin = q.front();
//            ret = max(ret, end.second - begin.second + 1);
//
//            queue<pair<TreeNode*, unsigned int>> tmp;
//            // 将当前层的下一层入队列
//            while (!q.empty())
//            {
//                auto cur = q.front();   q.pop();
//                if (cur.first->left)   tmp.push({ cur.first->left, 2 * cur.second });
//                if (cur.first->right)  tmp.push({ cur.first->right, 2 * cur.second + 1 });
//            }
//            q = tmp;
//        }
//        return ret;
//    }
//};

// 三指针解法
//class Solution {
//public:
//    void sortColors(vector<int>& nums)
//    {
//        int n = nums.size();
//        qsort(nums, -1, n);
//    }
//    void qsort(vector<int>& nums, int left, int right)
//    {
//        int i = 0;
//        while (i < right)
//        {
//            if (nums[i] == 0)    swap(nums[++left], nums[i++]);
//            else if (nums[i] == 1)   i++;
//            else    swap(nums[--right], nums[i]);
//        }
//    }
//};

//class Solution {
//public:
//    int findPeakElement(vector<int>& nums)
//    {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] >= nums[mid - 1])  left = mid;
//            else    right = mid - 1;
//        }
//        return left;
//    }
//};
//class Solution 
//{
//public:
//    int missingNumber(vector<int>&nums)
//    {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] == mid) left = mid + 1;
//            else right = mid;
//        }
//        return left == nums[left] ? left + 1 : left;
//    }
//};

//const vector<pair<int, string>> valueSymbols = {
//        {1000, "M"},
//        {900,  "CM"},
//        {500,  "D"},
//        {400,  "CD"},
//        {100,  "C"},
//        {90,   "XC"},
//        {50,   "L"},
//        {40,   "XL"},
//        {10,   "X"},
//        {9,    "IX"},
//        {5,    "V"},
//        {4,    "IV"},
//        {1,    "I"},
//};
//class Solution {
//public:
//    string intToRoman(int num)
//    {
//        string ans;
//        auto it = valueSymbols.begin();
//        while (it != valueSymbols.end())
//        {
//            while (num >= it->first)
//            {
//                num -= it->first;
//                ans += it->second;
//            }
//            if (num == 0)    break;
//            ++it;
//        }
//
//        // for(const auto& [a, b] : valueSymbols)
//        // {
//        //     while(num >= a)
//        //     {
//        //         num -= a;
//        //         ans += b;
//        //     }
//        //     if(num == 0)    break;
//        // }
//        return ans;
//    }
//};
//
//const int N = 100010;
//long long arr[N], dp[N];
//int n, q;
//int main()
//{
//    cin >> n >> q;
//    // 读取数据
//    for (int i = 1; i <= n; i++) cin >> arr[i];
//    // 处理前缀和数组
//    for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        // 计算区间和
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//    return 0;
//}

//class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        // lsum[i] 表⽰：[0, i - 1] 区间所有元素的和
//        // rsum[i] 表⽰：[i + 1, n - 1] 区间所有元素的和
//        int n = nums.size();
//        vector<int> lsum(n), rsum(n);
//        // 预处理前缀和后缀和数组
//        for (int i = 1; i < n; i++)
//            lsum[i] = lsum[i - 1] + nums[i - 1];
//        for (int i = n - 2; i >= 0; i--)
//            rsum[i] = rsum[i + 1] + nums[i + 1];
//        // 判断
//        for (int i = 0; i < n; i++)
//            if (lsum[i] == rsum[i])
//                return i;
//        return -1;
//    }
//};

//class Solution
//{
//public:
//    int subarraysDivByK(vector<int>& nums, int k)
//    {
//        unordered_map<int, int> hash;
//        hash[0 % k] = 1; // 0 这个数的余数
//        int sum = 0, ret = 0;
//        for (auto x : nums)
//        {
//            sum += x; // 算出当前位置的前缀和
//            int r = (sum % k + k) % k; // 修正后的余数
//            if (hash.count(r)) ret += hash[r]; // 统计结果
//            hash[r]++;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int singleNumber(vector<int>& nums)
//    {
//        int ret = 0;
//        for (int i = 0; i < 32; i++)
//        {
//            int sum = 0;
//            for (auto e : nums)
//                if (((e >> i) & 1) == 1)  sum++;
//            sum %= 3;
//
//            if (sum == 1)    ret |= 1 << i;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    bool check(int* x, int* y)
//    {
//        for (int i = 0; i < 26; i++)
//            if (x[i] != y[i])    return false;
//        return true;
//    }
//    vector<int> findAnagrams(string s, string p)
//    {
//        vector<int> v;
//        int slen = s.size(), plen = p.size();
//        if (slen < plen) return v;
//        int hash1[26] = { 0 };
//        for (auto& e : p)
//            hash1[e - 'a']++;
//        int hash2[26] = { 0 };
//        for (int left = 0, right = 0; right < slen; right++)
//        {
//            // 进窗口
//            hash2[s[right] - 'a']++;
//            int cur = right - left + 1;
//            // 判断
//            while (cur > plen)
//            {
//                // 出窗口
//                hash2[s[left] - 'a']--;
//                left++;
//                cur--;
//            }
//            if (check(hash1, hash2))  v.push_back(left);
//        }
//        return v;
//    }
//};
//
//int main()
//{
//    Solution su;
//    string s = "cbaebabacd", p = "abc";
//    vector<int> v = su.findAnagrams(s, p);;
//    for (int i = 0; i < v.size(); i++)
//    {
//        cout << v[i] << endl;
//    }
//    return 0;
//}

//class Solution {
//public:
//    int maxPower(string s)
//    {
//        unordered_map<int, int> hash;
//        int ret = 0;
//        int left = 0, right = 0;
//        for (; right < s.size(); right++)
//        {
//            hash[s[right]]++;
//            while (hash.size() > 1)
//            {
//                hash[s[left]]--;
//                if (hash[s[left]] == 0)
//                    hash.erase(s[left]);
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};
//int main()
//{
//    Solution su;
//    string str = "leetcode";
//    int res = su.maxPower(str);
//    cout << res << endl;
//    return 0;
//}
// 替换后的最长重复字符
//class Solution {
//public:
//    int characterReplacement(string s, int k)
//    {
//        int ret = 0, n = s.size();
//        int hash[26] = { 0 };
//        int left = 0, right = 0;
//        for (; right < n; right++)
//        {
//            // 进窗口
//            hash[s[right] - 'A']++;
//            ret = max(ret, hash[s[right] - 'A']);
//            // 判断
//            while (right - left + 1 - ret > k)
//            {
//                // 出窗口
//                hash[s[left] - 'A']--;
//                left++;
//            }
//        }
//        return right - left;
//    }
//};

//class Solution {
//public:
//    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
//        int ret = 0;
//        for (int i = 1; i < timeSeries.size(); i++)
//        {
//            int tmp = timeSeries[i] - timeSeries[i - 1];
//            if (tmp >= duration) ret += duration;
//            else ret += tmp;
//        }
//        return ret + duration;
//    }
//};
//
//class Solution {
//public:
//    vector<int> getLeastNumbers(vector<int>& nums, int k)
//    {
//        srand(time(NULL));
//        qsort(nums, 0, nums.size() - 1, k);
//        return { nums.begin(), nums.begin() + k };
//    }
//    void qsort(vector<int>& nums, int l, int r, int k)
//    {
//        if (l >= r) return;
//        // 1. 随机选择⼀个基准元素 + 数组分三块
//        int key = getRandom(nums, l, r);
//        int left = l - 1, right = r + 1, i = l;
//        while (i < right)
//        {
//            if (nums[i] < key) swap(nums[++left], nums[i++]);
//            else if (nums[i] == key) i++;
//            else swap(nums[--right], nums[i]);
//        }
//        // [l, left][left + 1, right - 1] [right, r]
//        // 2. 分情况讨论
//        int a = left - l + 1, b = right - left - 1;
//        if (a > k) qsort(nums, l, left, k);
//        else if (a + b >= k) return;
//        else qsort(nums, right, r, k - a - b);
//    }
//    int getRandom(vector<int>& nums, int l, int r)
//    {
//        return nums[rand() % (r - l + 1) + l];
//    }
//};

//class Solution
//{
//    int tmp[50010];
//public:
//    int reversePairs(vector<int>& nums)
//    {
//        return mergeSort(nums, 0, nums.size() - 1);
//    }
//    int mergeSort(vector<int>& nums, int left, int right)
//    {
//        if (left >= right) return 0;
//        int ret = 0;
//        // 1. 先根据中间元素划分区间
//        int mid = (left + right) >> 1;
//        // [left, mid] [mid + 1, right]
//        // 2. 先计算左右两侧的翻转对
//        ret += mergeSort(nums, left, mid);
//        ret += mergeSort(nums, mid + 1, right);
//        // 3. 先计算翻转对的数量
//        int cur1 = left, cur2 = mid + 1, i = left;
//        while (cur1 <= mid) // 降序的情况
//        {
//            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
//            if (cur2 > right)
//                break;
//            ret += right - cur2 + 1;
//            cur1++;
//        }
//        // 4. 合并两个有序数组
//        cur1 = left, cur2 = mid + 1;
//        while (cur1 <= mid && cur2 <= right)
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
//        while (cur1 <= mid) tmp[i++] = nums[cur1++];
//        while (cur2 <= right) tmp[i++] = nums[cur2++];
//        for (int j = left; j <= right; j++)
//            nums[j] = tmp[j];
//        return ret;
//    }
//};

//class Solution {
//public:
//    bool Check(string& s, int left, int right)
//    {
//        while (left < right)
//        {
//            if (s[left] != s[right]) return false;
//            left++;
//            right--;
//        }
//        return true;
//    }
//    bool validPalindrome(string s)
//    {
//        int left = 0, right = s.size() - 1;
//        while (left < right)
//        {
//            if (s[left] == s[right])
//            {
//                left++; right--;
//            }
//            // 只有一次删除元素的机会，可以删除left位置，也可以删除right位置
//            else    return Check(s, left + 1, right) || Check(s, left, right - 1);
//        }
//        return true;
//    }
//};

//class Solution {
//public:
//    // 计算当前数的下一位
//    int bitSum(int n)
//    {
//        int sum = 0;
//        while (n)
//        {
//            int tmp = n % 10;
//            sum += tmp * tmp;
//            n /= 10;
//        }
//        return sum;
//    }
//    bool isHappy(int n)
//    {   // 快慢指针
//        int slow = n, fast = bitSum(n);
//        while (slow != fast)
//        {
//            slow = bitSum(slow);
//            fast = bitSum(bitSum(fast));
//        }
//        return slow == 1 ? true : false;
//    }
//};

//class Solution {
//public:
//    int maxArea(vector<int>& height)
//    {
//        int left = 0, right = height.size() - 1, ans = 0;
//        while (left < right)
//        {
//            int v = min(height[left], height[right]) * (right - left);
//            ans = max(ans, v);
//
//            if (height[left] < height[right])
//                left++;
//            else
//                right--;
//        }
//        return ans;
//    }
//};

//class Solution {
//public:
//    vector<int> productExceptSelf(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<int>v(n);
//        vector<int>fx(n, 1);
//        vector<int>gx(n, 1);
//        // 前缀积
//        for(int i= 1;i< n;i++)
//            fx[i] = fx[i - 1] * nums[i - 1];
//        // 后缀积
//        for(int i=n-2;i >= 0;i--)
//            gx[i] = gx[i + 1] * nums[i + 1]; 
//        for (int i = 0; i < n; i++)
//            v[i] = fx[i] * gx[i];
//        return v;
//    }
//};

//class Solution {
//public:
//    int subarraySum(vector<int>& nums, int k)
//    {
//        sort(nums.begin(), nums.end());
//        int left = 0, right = 0;
//        int sum = 0, cnt = 0;
//        for (; right < nums.size(); right++)
//        {
//            sum += nums[right];
//            if (sum < k) continue;
//            else if (sum > k)
//            {
//                while (sum > k)
//                {
//                    sum -= nums[left];
//                    left++;
//                }
//            }
//            else
//            {
//                cnt++;
//            }
//        }
//        return cnt;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> merge(vector<vector<int>>& intervals)
//    {
//        if (intervals.size() == 0)   return {};
//        sort(intervals.begin(), intervals.end());
//        vector<vector<int>> vv;
//        for (int i = 0; i < intervals.size(); i++)
//        {
//            int left = intervals[i][0], right = intervals[i][1];
//            if (!vv.size() || vv.back()[1] < left)
//                vv.push_back({ left, right });
//            else    // 合并
//                vv.back()[1] = max(vv.back()[1], right);
//        }
//        return vv;
//    }
//};

//class Solution {
//public:
//    int evalRPN(vector<string>& tokens)
//    {
//        stack<int> st;
//        for (int i = 0; i < tokens.size(); i++)
//        {
//            if (tokens[i] == "+" || tokens[i] == "-"
//                || tokens[i] == "*" || tokens[i] == "/")
//            {
//                int B = st.top();
//                st.pop();
//                int A = st.top();
//                st.pop();
//                int C = 0;
//                if (tokens[i] == "+")    C = A + B;
//                else if (tokens[i] == "-")   C = A - B;
//                else if (tokens[i] == "*")   C = A * B;
//                else    C = A / B;
//                st.push(C);
//            }
//            else
//                st.push(stoi(tokens[i]));
//        }
//        return st.top();
//    }
//};

//class MinStack {
//public:
//    MinStack() {}
//    void push(int val)
//    {
//        _stack.push(val);
//        if (_minstack.empty() || val <= _minstack.top())
//            _minstack.push(val);
//    }
//    void pop()
//    {
//        if (_stack.top() <= _minstack.top())
//            _minstack.pop();
//        _stack.pop();
//    }
//    int top()
//    {
//        return _stack.top();
//    }
//    int getMin()
//    {
//        return _minstack.top();
//    }
//    stack<int> _minstack;
//    stack<int> _stack;
//};

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* x = new ListNode(-1);
        ListNode* prev = x;
        prev->next = head;
        ListNode* cur = head, * _next = head->next;
        ListNode* nnext = _next->next;

        while (cur && _next)
        {
            prev->next = _next;
            _next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if (cur)     _next = cur->next;
            if (_next)   nnext = _next->next;
        }
        return x->next;
    }
};
